デバッグをしている間はスキャナの性能というものは通常それほど重要ではなく、Flex のデフォルトの設定で十分です。しかしデバッグ終了後は、スピードもしくはサイズの面でスキャナを最適化したくなることもあるでしょう。ここでは、スキャナを最適化するのによく使われる手法をいくつか紹介します。
多くのプログラムは字句解析の処理に多くの時間を費やします。したがって、スキャナの最適化はかなり大きな性能改善に結びつくことが多いのです。Flex によるスキャナは Lex によるスキャナと比較するとかなり高速になる傾向がありますが、特定の構成もしくはアクションによって、性能に大きな影響を与えることができます。注意すべき点は以下のとおりです。
どのような圧縮も結果的にスキャナの性能を悪くします。したがって、スピードのことが心配であるならば、常にコマンドラインで
-f オプションもしくは -F オプションを使ってください。テーブルの圧縮およびスピードに関連するオプションに関する詳細な議論については、***ページの
5.3 節「テーブルの圧縮とスキャナのスピード」を参照してください。
これはスピードに対して最も大きな影響を及ぼすもので、これが使われるとすべてのマッチ処理が遅くなります。というのは、スキャナはマッチする前の状態に自身を復旧する必要があるからで、このようなことが必要ない場合と比較して、より多くの内部的な保守作業を行わなければならないからです。スピードが重要な場合には、これを使わないようにしてください。
スキャナがあるテキストにマッチするために「逆行」しなければならないことを、バックトラッキングといいます。これはスキャナの性能に悪い影響を及ぼしますので、スピードが最も重要である場合には避けるべきものです。圧縮されたテーブルは常にバックトラッキングを発生させるので、-f
オプションもしくは -F オプションを使わない場合は、ルールからバックトラッキングを削除しようとするのは時間の無駄です。スキャナからバックトラッキングを削除することに関するより詳細な情報については、***ページの
6.1.1 節「バックトラッキング(backtracking)の削除」を参照してください。
可変長後続コンテキストとは、あるルールの先頭部分と末尾部分の両方が固定長でないような場合を指します。これは、性能の観点からは
REJECT と同じくらい悪影響を持つもので、可能な場合にはいつでも避けるべきです。この例を示すと、以下のようになります。
^ 演算子は性能に不利な影響を及ぼします。スピードが最も重要な場合には、これを使わないでください。
yymore を使うと性能を劣化させます。スピードが最も重要な場合には、これを使わないでください。
スキャナの性能は、それがマッチするテキストの長さによっても影響を受けます。常に長い文字列にマッチするような場合には、スキャナは高速に実行されます。というのは
yytext 環境をセットアップする必要がないからです。ほとんどの時間は、内部の高速なマッチング・ループの中で費やされることになります。
Flex は NUL を含むトークンをマッチするのに時間がかかります。この場合には、短かいテキストにマッチするようルールを記述するほうが良いでしょう。
スキャナからバックトラッキングを削除することは、スキャナの性能にかなりの影響をもたらします。残念ながら、バックトラッキングの削除はかなり複雑な作業になる可能性があります。例えば、
コマンドライン・オプション -b を使うことで、バックトラッキングを発生させている原因に関する情報を知ることができます。これにより、バックトラッキングに関する情報を含む lex.backtrack というファイルが生成されます。上記の例の場合は、このファイルは以下のような情報を含みます。
State #7 is non-accepting -
associated rule line numbers:
2
3 4
out-transitions: [ d ]
jam-transitions: EOF [ \000-c e-\177 ]
State #9 is non-accepting -
associated rule line numbers:
3
4
out-transitions: [ e ]
jam-transitions: EOF [ \000-d f-\177 ]
Compressed tables always backtrack.
バックトラッキングを削除するためには、それが関与している状態をキャッチするルールを加える必要があります。これは、スキャナのスピードには影響を与えないということに注意してください。スキャナのスピードは、ルールの数や複雑さとはほぼまったく無関係です。
バックトラッキングを削除するためにルールを追加する方法には2種類あります。最初の方法は以下のようなルールを追加することです。
これに付随する問題の1つに、複雑なスキャナではバックトラッキング問題はカスケードする傾向があるので lex.backtrack 内の情報が混乱をもたらすことがありえるということがあります。しかし、バックトラッキングの原因は通常2、3個のルールにしぼることが可能なので、バックトラック・データを調べようと努力するだけの値打ちはあります。
Flex は、サイズの小さいスキャナよりもむしろ非常に高速なスキャナを作成することを目標としていますが、いずれにしても、作成されるテーブルのサイズは Lex によるそれと比較しても通常はかなり小さいものになります。
デフォルトでは Flex は可能な限りサイズの小さいスキャナを作成します。これはコマンドラインで -Cem を使うのと同等です。デフォルトを使うのであれば、コマンドライン・オプションを気にする必要はありません。
さらにテーブルのサイズを小さくするには、より大きなテキスト・グループにマッチするルールを使い、字句の値を認識するには C のサブルーチンを使うのが最も良い方法です。この良い例がコンパイラで、そこでは以下のようなルールを与えることができます。
Copyright (C) 1992, 1993 Free Software Foundation
Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.
Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.
Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Free Software Foundation.
日本語訳:市川和久
Japanese translation by Kazuhisa Ichikawa (ki@home.email.ne.jp)